package com.sxu.fighting.day1;

public class Test5 {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        if (n == 0)
            return;

        // 处理k大于数组长度的情况
        k = k % n;
        if (k == 0)
            return;

        // 1. 保存后k个元素
        int[] arr = new int[k];
        for (int i = 0; i < k; i++) {
            arr[i] = nums[n - k + i]; // 从n-k位置开始复制
        }

        // 2. 将前n-k个元素向后移动k位（从后向前移动）
        for (int i = n - k - 1; i >= 0; i--) {
            nums[i + k] = nums[i]; // 避免覆盖未处理的元素
        }

        // 3. 将保存的元素放到数组前面
        for (int i = 0; i < k; i++) {
            nums[i] = arr[i];
        }
    }

    // 反转法
    public void rotate2(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        if (k == 0) return;

        // 三次反转完成旋转
        reverse(nums, 0, n - 1);  // 反转整个数组
        reverse(nums, 0, k - 1);  // 反转前k个元素
        reverse(nums, k, n - 1);   // 反转剩余元素
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}
